package org.example.l0;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class jump {

    @Test
    void aa() {
        int[] nums = {2,3,1,1,4};
        int i = jumpV0(nums);
        System.out.println(i);
    }

    public int jumpV0(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, Integer.MAX_VALUE >> 1);
        dp[0] = 0;

        for (int i = 0; i < len; i++) {
            for (int j = 1; j <= nums[i]; j++) {
                if (i + j < len) {
                    dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                }
            }
        }

        return dp[len - 1];
    }

    public int jumpV2(int[] nums) {
        int p = nums.length - 1, step = 0;
        for (; p > 0; ) {
            for (int i = 0; i < p; i++) {
                if (i + nums[i] >= p) {
                    p = i;
                    step++;
                    break;
                }
            }
        }

        return step;
    }

    public int jumpV3(int[] nums) {
        int len = nums.length, end = 0, maxP = 0, step = 0;
        for (int i = 0; i < len - 1; i++) {
            maxP = Math.max(maxP, nums[i] + i);
            if (i == end) {
                step++;
                end = maxP;
            }
        }

        return step;
    }


    public boolean canJump(int[] nums) {
        int len = nums.length, max = 0;

        for (int i = 0; i < len; i++) {
            if (i > max) {
                return false;
            }

            max = Math.max(max, i + nums[i]);
            if (max > len - 1) {
                return true;
            }
        }

        return false;
    }

    @Test
    void run2() {
        int[] nums = {3,2,1,0,4};
        canJumpV2(nums);
    }

    public boolean canJumpV2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }

        int len = nums.length;
        boolean[] dp = new boolean[len];
        dp[0] = nums[0] != 0;

        for (int i = 0; i < len; i++) {
            int v = nums[i];
            for (int j = 1; j <= v; j++) {
                if (i + j > len - 1) {
                    break;
                }
                dp[i + j] = dp[i];
            }
        }

        return dp[len - 1];
    }

}
